package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class MagicDictionary {

	String[] strings = null;
	HashMap<Integer, ArrayList<String>[]> allString = null;

	/** Initialize your data structure here. */
	public MagicDictionary() {

	}

	/** Build a dictionary through a list of words */
	public void buildDict(String[] dict) {
		allString = new HashMap<>();
		for (String string : dict) {
			if (!allString.containsKey(string.length())) {
				ArrayList<String>[] kong = new ArrayList[string.length()];
				for (int i = 0; i < kong.length; i++) {
					kong[i] = new ArrayList<>();
				}
				allString.put(string.length(), kong);
			}
			ArrayList<String>[] kong = allString.get(string.length());
			for (int i = 0; i < kong.length; i++) {
				String sub = string.substring(0, i) + string.substring(i + 1);
				kong[i].add(sub);
			}
		}
		strings = dict;
	}

	/**
	 * Returns if there is any word in the trie that equals to the given word
	 * after modifying exactly one character
	 */
	public boolean search(String word) {
		ArrayList<String>[] kong = allString.get(word.length());
		if (kong == null) {
			return false;
		}
		int needCount = 1;
		if (Arrays.binarySearch(strings, word) >= 0) {
			needCount = 2;
		}

		for (int i = 0; i < word.length(); i++) {
			String sub = word.substring(0, i) + word.substring(i + 1);
			if (kong[i].contains(sub)) {

				// return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		MagicDictionary magicDictionary = new MagicDictionary();
		magicDictionary.buildDict(new String[] { "hello", "hallo", "leetcode" });
		System.out.println(magicDictionary.search("hello"));
		System.out.println(magicDictionary.search("hhllo"));
		System.out.println(magicDictionary.search("hell"));
		System.out.println(magicDictionary.search("leetcoded"));
	}
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary(); obj.buildDict(dict); boolean
 * param_2 = obj.search(word);
 */
